/*
 * top_k.cpp
 * Copyright (C) 2014 edward <libo@tencent.com>
 *
 * Distributed under terms of the MIT license.
 */

#include <algorithm>
#include <time.h>
#include <stdio.h>

bool cmp(int a, int b) {
 return a > b;
}
using namespace std;
/*
 * @brief return top count <= k
 */
int top_k(int input[], int sz, int output[], int k) {
 if (k < 0 || sz <= 0)
   return -1;
 int count = 0;
 for (int i = 0; i < sz; ++i) {
   if (count < k ||
       (count == k && input[i] > output[0])) { 
      output[count] = input[i];
      ++count;
      push_heap(&output[0], &output[count], cmp);
      if (count > k) {
        pop_heap(&output[0], &output[count], cmp);
        --count;
      }
   }
 }
 return count;
};

int main() {
  const int sz = 10000;
  const int k = 10;
  int input[sz];
  int output[k + 1];
  for (int i = 0; i < sz; ++i) {
    srand(time(NULL) + i);
    input[i] = rand() % sz;
    printf("%d\n", input[i]);
  }
  int ret_k = top_k(input, sz, output, k);
  if (ret_k > 0) {
    for (int i = 0; i < ret_k; ++i) {
      printf("-%d\n", output[i]);
    } 
  }
}
